package l.l.w.leetcode._079WordSearch;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * Created by llw on 2017/11/26.
 */
public class _079WordSearch {
    public boolean exist(char[][] board, String word) {
        if(board==null || board.length < 1) return false;
        int m = board.length;
        int n = board[0].length;
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                if(board[i][j] == word.charAt(0)){
                    if(check(board,i,j,word,m,n)) return true;
                }
            }
        }
        return false;
    }
    private boolean check(char[][] board,int startI, int startJ, String word,int m, int n){
        Stack<int[]> stack = new Stack<int[]>();
        stack.push(new int[]{startI,startJ,1});
        List<Integer> used = new LinkedList<Integer>();
        used.add(startI * n + startJ);
        if(word.length() == 1) return true;
        while(!stack.isEmpty()){
            int[] index = stack.pop();
            int i = index[0];
            int j = index[1];
            int k = index[2];
            if(k == word.length()) return true;
            used.add((i)*n+j);
            //上下左右合适的加入栈中
            int num = 0;
            if(i - 1 >= 0 && board[i-1][j] == word.charAt(k) && !used.contains((i-1)*n+j)) {
                stack.push(new int[]{i-1,j,k+1});

                num++;
            }
            if(j - 1 >= 0 && board[i][j-1] == word.charAt(k) && !used.contains((i)*n+j-1)) {
                stack.push(new int[]{i,j-1,k+1});
                num++;
            }
            if(i + 1 < m && board[i+1][j] == word.charAt(k) && !used.contains((i+1)*n+j)){
                stack.push(new int[]{i+1,j,k+1});
                num++;
            }
            if(j + 1 < n && board[i][j+1] == word.charAt(k) && !used.contains((i)*n+j+1)) {
                stack.push(new int[]{i,j+1,k+1});
                num++;
            }
            if(num >= 1){

            }else{
                used.remove(new Integer(i*n+j));
            }
        }
        return false;
    }

    public static void main(String[] args) {
        char[][] chars = {{'A','B','C','E'},{'S','F','E','S'},{'A','D','E','E'}};
//        char[][] chars = {{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
//        char[][] chars = {{'C', 'A', 'A'}, {'A', 'A', 'A'}, {'B', 'C', 'D'}};
//        [["A","B","C","E"],["S","F","E","S"],["A","D","E","E"]]
//        "ABCESEEEFS"
        boolean result = new _079WordSearch().exist(chars, "ABCESEEEFS");
        System.out.println(result);
    }
}
